package com.leetcode.offer.chapter5;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author Dennis Li
 * @date 2020/7/14 21:59
 */
public class MajorityElement_39 {

    public static void main(String[] args) {
        int[] ints = {1, 2, 3, 2, 2, 2, 5, 4, 2};

        System.out.println(majorityElement(ints));
    }

    public static int majorityElement(int[] nums) {
        int len = nums.length;
        int half = len >> 1;
        //int max = 1; // 设置为1，因为至少出现一次
        // 建立合理的map大小
        Map<Integer, Integer> map = new HashMap<>((int) (len / 0.75 + 1.0f));
        for (int i = 0; i < len; i++) {
            int now = nums[i];
            map.put(now, map.getOrDefault(now, 0) + 1);
            if (map.get(now) > half) return now;
        }
        // 只有一个元素
        return nums[0];
    }

    public int easyWay(int[] nums) {
        // 出现次数超过一半，那么排序后超过一半的数一定在中间
        // 注意思考题目和给的数据之间的联系
        new StringBuffer();
        new StringBuilder();
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    // 摩尔投票法
    public int mole(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            // 最后如果超过一半，那么票数一定不为0，退出循环
            if(votes == 0) x = num;
            // 判断当前选举者是否与当前数相等，相等则票数加1
            votes += num == x ? 1 : -1;
        }
        // 返回选举者
        return x;
    }
}
